package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

public class MSDSort {

    private MSDSort() {

    }

    public static void sort(String []arr){

        String[] temp=new String[arr.length];
        sort (arr,0,arr.length-1,0,temp);
    }

    /**
     * 使用辅助数组temp，减少内存的开销，对位于字符串left和right之间的部分的第radix位上的字符进行计数排数，递归调用
     * @param arr String
     * @param left 左边界
     * @param right 右边界
     * @param radix radix
     * @param temp 辅助数组
     */
    private static void sort(String[] arr,int left,int right,int radix,String[] temp){

        if(left>=right)return;

        //开始计数排序
        int range=256;
        //cnt数组的长度为range+1的原因：第r位的字符可能为空格，按照排序要求，空格字符应当小于所有的字符
        int []cnt=new int[range+1];
        int []index=new int[range + 2];
        //出现空格字符时，在cnt的位置为0
        for(int i=left;i<=right; i++){
            cnt[radix>=arr[i].length ()?0:arr[i].charAt (radix)+1]++;
        }
        //index[i,i+1)上的值为i
        for(int i=0;i+1<index.length;i++){
            index[i+1]=index[i]+cnt[i];
        }

        for(int i=left;i <= right; i++){
            int p=radix>=arr[i].length()?0:arr[i].charAt (radix)+1;
            temp[left+index[p]]=arr[i];
            index[p]++;
        }

        for(int i=left;i<=right;i++){
            arr[i]=temp[i];
        }
        /**
         * 经过一轮排序之后
         * index[0]=>index[1]
         * index[1]=>index[2]
         * ....
         * index[i]=>index[i+1]
         * 原来数组：[0,index.length)
         * 排序后的数组：[0,index.length-1)
         */
        for(int i=0;i+1<index.length-1;i++){
            //注意下标的偏移
            sort (arr,left+index[i],left+index[i+1]-1,radix+1,temp);
        }
    }

}
